#include "cplayer.h"
#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

namespace sokoban {

// Initialize static data members

const string CPlayer::DEADEND   = "deadend";

int CPlayer::nPushes = 0;

unordered_set<uint64_t> CPlayer::knownStates; 

CPlayer::CPlayer()
{
  nDLSearchCalls = 0;
}

string CPlayer::PlaceBoxes(const CBoard & board)
{
  return IDSearch(board);
}

string CPlayer::DLSearch(const CBoard & board, int depth, int depthLimit)
{
  LOG( L_DFS, "At DL Search depth %d and limit %d, board looks like", depth, depthLimit );
#if ( LOG_LEVEL & L_DFS )
  board.Print(); 
#endif
  LOG( L_DFS, "Board's value : %d", board.Value() );

  nDLSearchCalls++;

  if ( board.IsSolution() )
  {
    LOG( L_DFS, ">Board is solution!" );
    return board.GetPath();
  }
  else if ( board.Value() + depth >= depthLimit )
  {
    LOG( L_DFS, ">We hit depth limit with value %d and depth %d", board.Value(), depth );
    return DEADEND;                // We need to go deeper!
  }
  else
  {
    LOG( L_DFS, ">This is no solution, but we can go deeper. Expanding" );

    vector< CBoxMove > pBoxesMoves;
    board.FindPossibleBoxesMoves(pBoxesMoves);  // Possible actions from this state

    LOG( L_DFS, ">>Found %d moves from here", (int) pBoxesMoves.size() );

    // create all children boards and order them from the less valuable to
    // the most valuable.
    list< CBoard > children;

    for( uint i = 0 ; i < pBoxesMoves.size() ; i++ )
      children.push_back( CBoard( board, pBoxesMoves[ i ] ) );

    children.sort();

    // we do reverse iteration because higher value boards are at the end
    // of the list
    list< CBoard >::const_iterator itCh;

    LOG( L_DFS, "New order" );
    for( itCh = children.begin() ; itCh != children.end() ; itCh++ )
      LOG( L_DFS, "%d", (*itCh).Value() );

    string result( DEADEND );

    for( itCh = children.begin() ; itCh != children.end() ; itCh++ )
    {
      //LOG( L_DFS, ">>At depth %d, Expanding move %d out of %d", depthLimit, (i+1), pBoxesMoves.size() );

      if ( isStateKnown( *itCh  ) )
      {
        LOG( L_DFS, ">>>Pruning duplicate state" );
        continue;
      }
      else
      {
        result = DLSearch( (*itCh), depth + 1, depthLimit );

        if ( result.compare( DEADEND ) != 0 )
        {
          nPushes++;
          break;
        }
      }
    }
    //LOG( L_DFS, ">>No moves found, returning DEADEND" );

    /*
    for( itCh = children.begin() ; itCh != children.end() ; itCh++ )
      delete *itCh;
    */

    return result;
  }
  return DEADEND;
}

string CPlayer::IDSearch(const CBoard & board)
{
  int depth = 200; // assume there is no solution making less than 8 box-moves
  string result;

  for (;;) // assume there is a solution that we will find!
  {
    LOG( L_GAME, "Starting iteration of ID with depth limit = %d\n", depth );
    knownStates.insert( board.Hash() );
    result = DLSearch(board, 0, depth);
    depth += 2;
    if ( result.compare(DEADEND) != 0 )
    {
      LOG( L_GAME, "Solution found, with %d pushes after %d DLs!", nPushes, 
          nDLSearchCalls );
      return result;
    }
    knownStates.clear();
    LOG( L_GAME, "Finished iteration of ID with result = %s\n", result.c_str() );
  }

  return result;
}

bool CPlayer::isStateKnown( CBoard const & newState )
{
  uint64_t key = newState.Hash();

  unordered_set<uint64_t>::iterator it = knownStates.find(key);

  bool known = it != knownStates.end();

  if ( !known )
    knownStates.insert(key);

  return known;
}

/* namespace sokoban */ }
